/**
 * @Author：ming
 * @Date：2023/10/21 12:52 AM
 * @Filename：Lc547
 */

import java.util.HashSet;

/**
 * @author ming
 */
public class Lc547 {
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length;
        boolean[] visit = new boolean[cities];
        int province = 0;
        for (int i = 0; i < cities; i++) {
            if(!visit[i]){
                dfs(isConnected,cities,i,visit);
                province++;
            }
        }

        return province;
    }

    //深度优先
    public void dfs(int[][] isConnected,int cities,int i,boolean[] visit ){

        for (int j = 0; j < cities; j++) {
            if(isConnected[i][j]==1&&!visit[j]){
                visit[j]=true;
                dfs(isConnected,cities,j,visit);
            }
        }
    }
}
